/*
输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
 

限制：

1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 回溯 + 集合去重
class Solution {
public:
    vector<string> permutation(string s) {
        int n = s.size();
        visited.resize(n);
        string temp;
        backTrack(s, 0, n, temp);
        vector<string> res(rec.begin(), rec.end());
        return res;
    }
    void backTrack(const string& s, int i, const int& n, string& temp) {
        if (i == n) {
            rec.insert(temp);
            return;
        }
        for (int j{0}; j < n; ++j) {
            if (visited[j]) {
                continue;
            }
            visited[j] = true;
            temp.push_back(s[j]);
            backTrack(s, i + 1, n, temp);
            temp.pop_back();
            visited[j] = false;
        }
    }
private:
    set<string> rec;
    vector<int> visited;
};

// 回溯 + 优化递归函数
class Solution {
public:
    vector<string> permutation(string s) {
        int n = s.size();
        visited.resize(n);
        sort(s.begin(), s.end());
        string temp;
        backTrack(s, 0, n, temp);
        return res;
    }
    void backTrack(const string& s, int i, const int& n, string& temp) {
        if (i == n) {
            res.push_back(temp);
            return;
        }
        for (int j{0}; j < n; ++j) {
            // 1. s[j]已经用过了
            // 2. 如果s[j]==s[j-1]，s[j-1]还没用的话s[j]就不能用，也就是说，限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」
            if (visited[j] || (j > 0 && !visited[j - 1] && s[j - 1] == s[j])) {
                continue;
            }
            visited[j] = true;
            temp.push_back(s[j]);
            backTrack(s, i + 1, n, temp);
            temp.pop_back();
            visited[j] = false;
        }
    }
private:
    vector<string> res;
    vector<int> visited;
};

// 下一个排列
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> res;
        sort(s.begin(), s.end());
        do {
            res.push_back(s);
        } while (nextPermutation(s));
        return res;
    }
private:
    bool nextPermutation(string& s) {
        int i = s.size() - 2;
        // 从后往前找第一个升序
        while (i >= 0 && s[i] >= s[i + 1]) {
            --i;
        }
        // 找不到升序，说明当前s是完全的降序，即最大的序列
        if (i < 0) {
            return false;
        }
        int j = s.size() - 1;
        // 从后往前找第一个大于s[i]的s[j]
        while (j >= 0 && s[i] >= s[j]) {
            --j;
        }
        swap(s[i], s[j]);
        // 反转s[i+1]之后的所有元素
        reverse(s.begin() + i + 1, s.end());
        return true;
    }
};

// 下一个排列 - stl algorithm
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> res;
        sort(s.begin(), s.end());
        do {
            res.push_back(s);
        } while (next_permutation(s.begin(), s.end()));
        return res;
    }
};